Numerically Controlled Machining
Simulating numerically controlled (NC) machining, e.g., turning, boring, drilling, broaching, sawing, shaping, reaming, milling, tapping, grinding, is important in computer aided design (CAD) and computer aided manufacturing (CAM). During the simulation, a model of an object, e.g., a workpiece, is edited with a computer representation of a tool, e.g., an NC milling tool, and a set of motions, which simulate the machining process.
The simulation visualizes the model of the object and the representation of the tool on a display device to detect potential collisions between parts, such as the workpiece and the tool holder, and to verify a final shape of the object.
The final shape of the object is affected by the selection of the tool and the motions. Instructions for controlling the motions are typically generated using a computer aided manufacturing system from a graphical representation of a desired final shape of the object. The motions are typically implemented using numerical control programming language, also known as preparatory code or G-Codes, see the RS274D and DIN 66025/ISO 6983 standards.
The G-Codes generated by the computer aided manufacturing system can fail to produce an exact replication of the desired final shape. In addition, the motion of the tool and/or object is governed by motors of the NC machining system, which have limited speeds, ranges of motion, and abilities to accelerate and decelerate, so that the actual motions sometimes do not exactly follow the NC machining instructions.
Discrepancies between the actual final shape of the object and the desired final shape of the object can be small, and difficult to observe. In some situations, these discrepancies result in undesirable gouges or nicks in the surface of the final shape of the object with sizes on the order of a few micrometers in depth and width, and tens of micrometers in length.
Typically, a set of NC machine instructions is tested by machining a test object, e.g., a workpiece made of softer, less expensive material prior to machining the desired part. If visual inspection of the test workpiece locates undesirable discrepancies in the test workpiece, then the NC machining instructions are modified accordingly.
However, this manual testing is time consuming and expensive. Time for machining a single test workpiece may be on the order of hours and several iterations may be required before an acceptable set of NC machine instructions is attained. Thus, it is desirable to test for these discrepancies using computer-based simulation and rendering.
Tools
FIG. 1A shows a set of typical tools 102, 104, 106, and 108 used in NC machining. When a tool is moved relative to a workpiece 110, the tool carves material out of the workpiece. Here, the tools 102, 104, 106, and 108 remove material, commonly referred to as a “swept volume,” corresponding to surfaces 112, 114, 116, and 118 from the workpiece. The shape of the material removed by each tool is determined by the shape of the tool, and the path of the tool relative to the workpiece.
Swept Volumes
During machining, the tool moves relative to the workpiece according to a prescribed motion of the tool and/or workpiece, i.e., a tool path or an object path, where the path can include information about the relative position, orientation, and other shape data of the tool with respect to the workpiece.
As the tool moves along the tool path, the tool carves out a swept volume. During machining, as the tool moves along the tool path, a portion of a volume of the workpiece that is intersected by the swept volume of the tool is removed. This material removal can be modeled as a constructive solid geometry (CSG) difference operation, in which a portion of the workpiece is removed from the workpiece using a CSG subtraction operation of the swept volume from the workpiece.
FIG. 1B shows the swept volume 160 of a shape 150 that is moved along a path 152. The path 152 specifies a position of a particular point of the shape 150 as a function of time. The path can specify an orientation 156, 157, and 158 of the shape as a function of time. The path can also specify a scale of the shape or an arbitrary transformation of the shape as a function of time.
In FIG. 1B, the original position, orientation, and geometry of a shape 150 is transformed to a final position, orientation, and geometry of the shape 154 as the shape moves along the path 157.
FIG. 2A shows a linear path, in which a tool 202 is moved along a straight line 204.
FIG. 2B shows a circular arc path, in which a tip 210 of the tool 202 is moved along a circular arc 212, and an original axis direction 214 of the tool is transformed to a final axis direction 216 at the end of the path.
FIG. 2C shows a curved path, in which the tip 210 of the tool 202 is moved along a curve 220.
Other possible path forms include positioning the tool at a point, moving the tool along a sequence of lines known as a polyline, moving the tool along a spiral or helical curve, moving the tool along a polynomial curve, such as a quadratic Bezier curve or a cubic Bezier curve, or a sequence of polynomial curves known as a piecewise polynomial curve to name but a few. Any form of path that can be simulated can be considered, including a path defined by a procedure such as a path that is influenced by the shape or material composition of the workpiece.
Distance Fields
The distance field, d(p), of an object is a scalar field whose value at a point p in space is the distance from p to the surface of the object. Many possible distance fields are known in the prior art, but the most common is a Euclidean distance field where the distance field value at p is the minimum straight line distance from p to the surface of the object. Additionally, a distance field may be signed to distinguish the outside, inside and boundary of the object, e.g., the d(p)>0 inside, d(p)<0, and d(p)=0 at the surface.
Also a gradient vector of the distance field at p points in the direction of the minimum distance, and at the surface of the object the normalized gradient vector is equal to the normal vector of the surface. Distance fields are a form of implicit functions, and are an effective representation for rendering and editing shapes.
The point p in space that is of particular interest is a point where a value for distance field d equals zero, i.e., d=0. As referred herein, the set of points where the distance field is zero, i.e., the zero isosurface of the distance field, is a boundary of the object, e.g., the boundary of the workpiece, or the boundary of the swept volume.
Adaptively sampled distance fields (ADFs) use detail-directed sampling to provide a space and time efficient representation of the distance fields. ADFs store value samples of the distance field in a spatial hierarchy of cells, such as an octree. A spatial hierarchy of cells is a tree data structure wherein an initial node called the root cell encloses the entire volume of the ADF. Cells of the spatial hierarchy may be terminal leaves of the tree data structure, i.e., leaf cells, or may contain smaller child cells, such cells are called intermediate cells. The leaf cells of the spatial hierarchy may be labeled as interior leaf cells, i.e., completely interior to the boundary, exterior leaf cells, i.e., completely exterior to the boundary, or boundary leaf cells, i.e., containing the boundary of the object. Each cell is characterized by a size and position that allows the vertices at the corners of the cell to be readily computed, and hence a bounding box for the cell is defined.
Associated with each cell in the spatial hierarchy is the address or index in a memory or table of both the parent cell and any child cells. This gives rise to the common description of the spatial hierarchy of cells as a family tree, wherein a cell has ancestors, reaching back through the cell's parent cell and grandparent cell to the root cell, and a cell may have descendent cells such as children cells and grandchild cells until the leaf cells are reached.
Access to the information within the spatial hierarchy of cells is usually obtained through a method of recursion wherein the information query begins at the root cell and then recurse, or branches, to descendent cells by choosing a particular branch, i.e., child cell, of the tree data structure depending on some condition. For example, a method to find the leaf cells that contains a particular point in space starts with the root cell and then recurses to the child cell of each descendent cell that contains the point until the leaf cell that contains the point is reached.
Each cell in the spatial hierarchy of cells may contain distance data and a reconstruction method for reconstructing the portion of the distance field associated with the cell. Distance data can include the value of the distance field, as well as gradients and partial derivatives of the distance field at a set of points within the cell, e.g., at the vertices of the cell's bounding box. The distance field at any point within the cell may be reconstructed from the distance data as needed to reduce memory and computation requirements.
ADFs can be used to simulate machining using CSG operations. The workpiece to be machined and the tool can be represented as ADFs. The simulated machining process can generate an ADF of the simulated workpiece explicitly, for example by modifying an ADF of the workpiece. In this case the distance data associated with a cell may be modified by simulated machining, but the reconstruction method can remain constant.
Alternatively, the simulated workpiece can be represented implicitly as a composite ADF. Unlike the conventional ADF described above, a composite ADF does not store distance field value samples within each cell. Instead the composite ADF stores, within a spatial hierarchy of cells, a set of parameters for each cell needed to compute, by analytic or numerically means, the exact values of the distance fields at any point within the cell. The stored parameters can include, for example, a set of indices into an array of machining tools, which array the type, shape and relevant dimensions of the tool. Additionally the stored parameters can include, for example, a set of indices into an array of motions, which provides a type of the motion, the starting and ending point of the motion and any other useful information. Additionally the stored parameters can include, for example, operators used to combine the distance fields, such as CSG subtraction for machining simulation. The parameters can be used to determine reconstruction functions that can be used in combination to compute or reconstruct the swept volume distance field within the cell. A swept volume distance field is defined to represent the swept volume generated by moving the machining tool along the path, where the swept volume distance field is defined in a continuous manner according to a swept volume reconstruction method. The swept volume reconstruction method can reconstruct the swept volume distance field at a sample point.
FIG. 3 shows a 2D composite ADF 300 that includes a spatial hierarchy of cells, e.g., 301, 302 and 303, representing portions of the volume of the workspace as well as distance fields whose boundaries are indicted. In this example, the boundaries of distance fields 304-307 are planes that defined the boundary of the initial workpiece. Distance fields 308-310 are the boundaries of three distance fields representing sweeps of a ball end tool 106. Each cell in the composite ADF is associated with a subset of the set of distance fields representing the original workpiece and the swept volumes of the tool. For example, the subset of the set of distance fields associated with cell 311 includes distance fields 304, 308, and 309 that together determine the composite ADF surface within cell 311. Also associated with the cell is a procedural reconstruction method, such as CSG difference, for combining the subset of the set of distance fields to reconstruct the composite distance field of the workpiece. The composite surface is defined to be the simulated boundary of the workpiece including patches of the boundaries of the original workpiece distance fields and the swept tool distance fields.
It is preferred that the stored distance field parameters for each cell includes only references to distance fields that actually form the composite boundary of the machined workpiece, rather than include references to all distance fields in the simulation, or all distance fields that have a portion of their boundary within the cell. By this means the number of calculations needed to perform geometric operations, e.g., rendering, can be minimized.
Rendering of Composite ADFs
Rendering of composite ADFs employs some methods and terminology common to all 3D computer graphics. Rendering of 3D objects into an image involves a number of coordinate systems related by transformation matrices. As shown in FIG. 4 composite ADF 401, whose origin and orientation are shown by axis lines 402 can be defined within a homogeneous world space coordinate system, hereafter world space, whose origin and orientation are given by axes lines 403. World space coordinates often employ real dimensions such as millimeters or miles and a 4×4 matrix called an ADF matrix can be used to map ADF coordinates to world space coordinates. A virtual camera 404, at some position and orientation relative to the world space coordinates, defines an eye space coordinate system whose origin and orientation are given by axes lines 405. Coordinates of points in world space can be transformed into eye space using a 4×4 viewing matrix.
Associated with the camera is a viewing frustum 406 that delimits the portion of world space that can be seen by the camera. If the camera model uses prospective projection to replicate the common experience that farther objects appear smaller than nearer objects, then the viewing frustum is in the shape of a truncated pyramid 406. The apex angle of the frustum is determined by the camera's field of view. There are alternative projection transformations such as orthographic project wherein the viewing frustum is rectangular in shape.
The 4×4 projection matrix can be used to transform from eye space coordinates to clip space coordinates. The minimum depth 407 and maximum depth 408 of the viewing frustum are conventionally known as the near and far clipping planes, respectively.
All of the 3D objects within the viewing frustum can be visible in the rendered image 409. The transformation from clip space to the screen space is determined by a viewport matrix that defines the image origin and image width and height in units of pixels. The image 409 can include several memory arrays known as frame buffers that have storage for various values associated with each image pixel. The most essential of these is a color buffer that holds the red, green and blue color components, and possibly the transparency or alpha, of each pixel. Prior to rendering the image, the color buffer is usually cleared to a chosen background color, for example black, to remove any color values associated with an earlier use of the buffer.
Another commonly used buffer is the z buffer which holds a depth associated with each pixel in screen space, such that an object at the near clipping plane has a depth of 0.0 and at the far clipping plane has a depth of 1.0, e.g., the depth is normalized to the range [0, 1]. The function of the depth buffer is to enable correct occlusion in the rendered image as described below. Prior to rendering the image the z buffer is usually cleared to some large depth value, typically 1.0.
The rendering of a composite ADF as an image can be performed by a number of methods, for example object-order ray casting or image-order ray casting as shown schematically in 2-D in FIG. 4. For example, during image-order ray casting method, rays are computationally emitted from each pixel in the image and propagated through the viewing frustum until the rays either intersect the boundary of the composite ADF, or reach the far clipping plane of the view frustum. A ray can be equivalent to a parametric line with a time-like coordinate t such that a position of the ray in 3D space is defined by R(t)=R0+Rd t where R0 is the origin of the ray and Rd is the direction vector of the ray. The rays are propagated through the composite ADF by first finding the closest cell having a lowest t that the ray intersects. If the closest cell is an intermediate cell, then the child cells of the intermediate cell are recursively tested for ray intersection until the ray intersects the closest leaf cell. If the leaf cell is not a boundary leaf cell, then the cell does not include the boundary of the composite ADF. The method then looks for a next leaf cell along the ray.
As an example, a ray 411 propagates through the viewing frustum without intersecting any cells. Hence, pixel corresponding to the ray 411 remains set to the background color. Ray 412 intersects the root cell of the spatial hierarchy. In this example the root cell is an intermediate cell and all immediate children. Eventually the recursion reaches cell 425 which is an exterior leaf cell. The method then searches for the next cell along ray 412. In this example, there are no other cells so the pixel corresponding to the ray 412 remains with the background color.
Now consider ray 413 which is associated with a screen pixel 414. After intersecting several intermediate and exterior leaf cells, the ray 413 intersects cell 415 which is a boundary leaf cell and is shown enlarged in the inset of FIG. 4. Cell 415 includes the boundaries of distance fields 416, 417, and 418, wherein 416 is a planar distance field representing the original workpiece surface, and 417 and 418 are the boundaries of distance fields corresponding to two sweeps of a ball end tool 106. The process of determining if a ray intersects the boundary of the composite ADF within a cell can involve first determining the ray coordinate, tfront and tback, of the intersection of the ray with the front boundary face 419 of the cell and back boundary face 420 of the cell, respectively. If tfront>tback, then the ray has missed the cell and the next ray is processed.
For rays that intersect the cell, the second step of image-order ray casting can begin by determining the points of intersection 421, 422, and 423, where, e.g., the ray 413 intersects the boundaries of distance fields 418, 416 and 417, respectively, associated with cell 415. Due to the subtractive nature of simulation a point p is only on the surface of the composite ADF. The point p is on the boundary of one distance field and inside of all of the others, i.e., if and only if di(p)=0, dj(p)>0 for i,jε[0, N), i≠j, where N is the number of distance field boundaries within the cell. Therefore, the values of the distance fields 416-418 can be determined for the intersection points 421-423 and the point with the minimum value of the ray parameter t that meets the above condition is the composite ADF surface point for that ray. In this example, the point 423 meets the condition and is known as a pixel fragment in the terminology of 3D computer graphics.
After the pixel fragment, e.g., the point 423, is determined, the normal vector of the surface is computed from the gradient of the distance field. The color and brightness of the pixel associated with the ray are determined from the material properties of the surface, e.g., ambient, diffuse and specular colors, plus material shininess, usually modified by using a lighting model, e.g. Phong or Blinn, that takes account of the dot product of the surface normal vector with a lighting vector as well as the light color. Typically, Phong lighting is used for plastics and, Blinn lighting is used for metals. Finally, the color and z value of the fragment are written into the color and z buffers, respectively.
The coordinates of fragments of the ADF or composite ADF are usually processed in a screen or image coordinate system. However, one skilled in the art will readily recognize that the coordinates of the fragment can be transformed from screen space back to world space by an inverse transformation that makes use of the mathematical inverses of the viewport, projection and viewing transformation matrices. The coordinates of the fragment in the world coordinate system corresponds to the surface of the ADF in the world coordinate systems.
Boundary Representations
A composite ADF is not the only possible representation of solid objects. The most common representation, used in most CAD software, is a boundary representation, or B-rep. A b-rep is a representation of an object by a set of non-lapping faces whose union represents the boundary of the object. A boundary representation has two parts, a topological description of the connectivity and orientation of vertices, edges and faces, and a geometric description for embedding these surface elements in space. A triangle mesh, commonly used in computer graphics, is an example of a boundary representation. In a triangle mesh each face is a triangle that is bounded by 3 edges that connect 3 vertices. A table, containing the positions of the all the vertices of the triangle mesh in world space, provides the geometric description of the boundary representation and a second table, wherein each entry is the indices of the 3 vertices that form a triangle of the triangular mesh, provides the topological description of the boundary representation.
Boundary representations are required to be closed, that is, the boundary representation must not have any gaps or holes. Additionally, the b-rep must be topological correct, that is, the b-rep must not have any dangling edges or faces that do not join other edges or faces to form a closed surface.
FIG. 5 shows an example conventional boundary representation of a tetrahedron. The tetrahedron can be described by four vertices, six edges and four triangular faces as follows: the vertices are 501, 502, 503, and 504; an edge 511 is a straight line with end vertices 501 and 502; an edge 512 is a straight line with end vertices 502 and 503; an edge 512 is a straight line with end vertices 502 and 503; an edge 513 is a straight line with end vertices 503 and 504; an edge 514 is a straight line with end vertices 501 and 504; an edge 515 is a straight line with end vertices 502 and 504; a face 520 is a triangle bounded by edges 512, 513, 515; a face 521 is a triangle bounded by edges 511, 515, 514; a face 522 is a triangle bounded by edges 511, 516, 512; and a face 523 is a triangle bounded by edges 513, 516, 514.
The boundary representation explicitly stores the boundary surfaces of the object. However, the side of a face that points toward the interior of the object is implicitly determined by the ordering of the vertices in the faces. In this example, a common right-hand ordering is used, in which the fingers of the right hand are oriented in the direction of the ordering of the vertices and the thumb points in the outward direction of the face. A method for determining if a point in space is interior or exterior to the boundary representation is to fire a ray from the point and count the number of faces that the ray intersects before reaching some large distance sufficiently great to be guaranteed to be outside the boundary representation. If the number of intersected faces is even, the point is outside the boundary representation, otherwise the point is inside.
A boundary representation is not limited to straight edges and flat faces. A boundary representation may also include, for example, parametric curves and faces such cubic B-splines and Bézier patches, respectively. These higher-order curves and surfaces enable solids with free-form boundaries to be represented in a compact way.
The rendering of boundary representations can be performed by 3D graphics hardware using a graphics application programming interface (API), such as OpenGL, and involves the same coordinate system and transformations that were describe above in the context of rendering composite ADFs. Each face of the boundary representation is rendered separately in an object-order fashion.
During rendering each face of the boundary can be converted into one or more flat polygons that can be passed to the graphics API. The graphics processor can transform the positions of the polygon vertices from world space to eye space by multiplication with the viewing transformation matrix, and then further transforms the positions to the clip space by multiplication by the projection matrix.
Additionally, a vector normal to the surface defined at each vertex is transformed by the transpose of the inverse of the upper 3×3 matrix of the viewing matrix. Clipping then occurs by discarding any faces that are not entirely within the clip volume (x, y, z)ε[−1, 1]. Any faces partially within the clip volume are clipped to the volume boundary. Vertices are then projected into screen space using a viewport matrix. Their (x, y, z) coordinates are now in the range of [0, screen_width) and [0, screen_height), and [0.0, 1.0] respectively. The transformed face is then rasterized; for each pixel within the screen region bounded by the transformed face a fragment of the boundary representation is generated whose position and color are determined by bilinear interpolation of the positions and colors of the face vertices. A z test is performed wherein the z value of each fragment is compared to the value already in the z buffer and if the value is less, i.e., closer, then the current z value and color are overwritten by the fragment values, and otherwise the fragment is discarded.
The normal vector can be determined for each fragment from the transformed normal vector defined at each vertex and interpolated to the screen position of the fragment. The color and brightness of the fragments can be determined from the material properties, e.g., ambient, diffuse and specular colors, plus material shininess, usually modified by using a lighting model, e.g. Phong or Blinn, that takes account of the dot product of the interpolated transformed normal vector with a lighting vector as well as the light color.
Many workpieces used in machining begin as simple shapes, such as rectangular solids or cylinders. However, another class of machining operations involves the finishing of cast workpieces. A cast workpiece, or casting, is produced by pouring molten metal into a mold to form a more complex initial workpiece. A common mold material is sand which is mixed with a weak adhesive and has itself been cast into a sand mold from other molds. Sand has the advantage of being inexpensive and heat resistant, and the finished casting can be easily extracted from the sand mold by simply breaking the sand apart.
Due to the relatively course texture of the sand a sand casting has a rough finish, and low dimensional accuracy. However, some surfaces of the workpiece need to have a smooth finish and high accuracy dimensions. For example, an automobile engine block is produced by sand casting and must be very accurate and smooth within the cylinders so that the piston rings can seal the cylinder, and the piston move correctly. Likewise, mounting holes must be tapped and sealing surfaces, where gaskets join separate components, must have a smooth and flat finish.
To achieve smooth surfaces and accurate dimensions some, or all, of the surfaces of the casting must be machined. Therefore it is important that a machining simulator is able to begin with a representation of the cast workpiece. However, a surface representation of the cast workpiece can be incompatible with representations of the motions of the tool. For example, the surface of the cast workpiece can be defined by explicit representation, e.g., a CAD boundary representation, and the motions of the tool can be defined by a surface having implicit representation, e.g., ADF representation.
The conventional methods convert an implicit object representation to explicit representation, or vice versa. However, the conversion process is time consuming and may have large memory requirements. Also, in the case of free-form surfaces, the conversion may result in a loss of accuracy. Accordingly, there is a need in the art to address abovementioned problems.